package com.practice.niuke.new_direct_basics.class08;

/**
 * 给定两个长度都为N的数组weights和values， weights[i]和values[i]分别代表
 * i号物品的重量和价值。 给定一个正数bag， 表示一个载重bag的袋子， 你装的物
 * 品不能超过这个重量。 返回你能装下最多的价值是多少？
 */
public class Code07_Knapsack {

    /**
     * 主方法(TODO：标记主函数)
     *
     * @param w
     * @param v
     * @param bag
     * @return
     */
    public static int getMaxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, 0, bag);
    }

    /**
     * 递归的尝试方法1（TODO：主要讲解的方法）：
     * （index... 最大价值）
     *
     * @param w        index号货物的重量存放在w数组中（w[index]当前货物的重量）
     * @param v        index号货物的价值存放在v数组中（v[index]当前货物的价值）
     * @param index    当前来到的货物号, index......后续所有货物自由选择
     * @param alreadyW 0...index-1已经做的决定，所形成的目前重量
     * @param bag      袋子可以承受的总重量（固定参数）
     * @return index......后续所有货物自由选择，返回最大的价值
     */
    public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
        // 已经超重，无效
        if (alreadyW > bag) {
            return -1;
        }
        // 重量没超，但是没货了
        if (index == w.length) {
            return 0;
        }
        // 不要当前的index货物，获得的总价值
        int p1 = 0 + process(w, v, index + 1, alreadyW, bag);
        // 要当前货物，后续获得的最大价值（此时还没有算上当前index货物的价值）
        int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
        int p2 = -1;
        // 后续过程有效
        if (p2next != -1) {
            // 要当前货物，获得的总价值(算上当前index货物的价值)
            p2 = v[index] + p2next;
        }
        // 返回当前决策的最大值（哪一种决策好一点）
        return Math.max(p1, p2);

    }

    public static int maxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, bag);
    }

    // 递归的尝试方法2：
    // 只剩下rest的空间了，
    // index...货物自由选择，但是只有rest的空间可用
    // 返回能够获得的最大价值
    public static int process(int[] w, int[] v, int index, int rest) {
        if (rest <= 0) { // base case 1
            return 0;
        }
        // rest >=0
        if (index == w.length) { // base case 2
            return 0;
        }
        // 有货也有空间
        // 没要当前的货物
        int p1 = process(w, v, index + 1, rest);
        int p2 = Integer.MIN_VALUE;
        if (rest >= w[index]) {
            // 要当前的货物
            p2 = v[index] + process(w, v, index + 1, rest - w[index]);
        }
        return Math.max(p1, p2);
    }

    public static int dpWay(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 1; rest <= bag; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest >= w[index]) {
                    dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
                }
            }
        }
        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7};
        int[] values = {5, 6, 3, 19};
        int bag = 11;
        System.out.println(maxValue(weights, values, bag));
        System.out.println(dpWay(weights, values, bag));
    }

}
